package com.changanw.code;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @author changanw
 * @version ncc1.0
 * @description  三数之和 给你一个整数数组 nums ，
 * 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，
 * 同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
 * 你返回所有和为 0 且不重复的三元组。
 * @date 2023/6/29 21:37
 */
public class Code15 {
  public List<List<Integer>> threeSum(int[] nums){
    //先对数组进行排序，保证数组顺序从大到小
    Arrays.sort(nums);
    Set<List<Integer>> lists = new HashSet<>();
    //固定一个位置，然后剩下的位置从固定位置的下一个，和最后一个开始移动，使用双指针
    for (int i = 0; i < nums.length; i++) {
      int left = i + 1;
      int right = nums.length - 1;
      while (left < right){
        if (nums[left] + nums[right] + nums[i] == 0){
          lists.add(Arrays.asList(nums[i],nums[left],nums[right]));
          left++;
          right--;
        } else if (nums[i] + nums[left] + nums[right] < 0) {
          left++;
        }else {
          right--;
        }
      }
    }
    List<List<Integer>> res = new ArrayList<>(lists);

    return res;
  }

  public static void main(String[] args) {
    Code15 code15 = new Code15();
    int nums[] = {-1,0,1,2,-1,-4};
    System.out.println(code15.threeSum(nums));
  }
}
